package com.wushijia.datastructure.tree2;

public class BinarySortedTree {

  private Node root;


  class Node {

    private long data;
    private Node left;
    private Node right;

    public Node(long data) {
      this.data = data;
    }
  }


  void insert(long data) {
    Node node = new Node(data);

    Node curr = root;

    Node parent;

    if (root == null) {
      root = node;
      return;
    }

    //循环找到合适的插入位置后返回
    while (true) {
      parent = curr;
      if (node.data < curr.data) {
        curr = curr.left;
        if (curr == null) {
          parent.left = node;
          return;
        }
      } else {
        curr = curr.right;
        if (curr == null) {
          parent.right = node;
          return;
        }
      }
    }
  }

//  void delete(long data) {
//
//    Node curr = root;
//    if (curr.data == data) {
//      if (curr.left.data == data) {
//        root = curr.right;
//      } else {
//
//      }
//    } else if (curr.data > data) {
//      curr = curr.left;
//    } else {
//      curr = curr.right;
//    }
//
//    //问题1：根节点删除后，谁将提升为根节点，比较左右节点，大的作为根节点
//    //问题2：如果有多个等值的节点，删除后如何重新排列
//    while (true) {
//      if ()
//    }
//
//  }

  /**
   * 后序遍历
   *
   * @param currNode
   */
  public void postOrder(Node currNode) {
    if (currNode == null) {
      return;
    }
    postOrder(currNode.left);
    postOrder(currNode.right);
    System.out.print(currNode.data + " ");
  }


}

